2nd Day - Courses ~ SAKURA Science exchange ~

Graph Theory

Instructor: Professor Suzuki (鈴木教授)

vertices
edges
degree: 點上有幾條邊
maximum degree
Hand Shaking Lemma: sum. of deg. is the twice of the edge
(PF: 在每個點旁邊的邊放tokens)
Odd pt. thm.: the number of the vertices with odd deg is even XD
Cycle: 踩點只能踩一次的圈圈
Problems: 最長的和最短的cycle?
simple graph: no self-loop
Bipartite graph: 分兩邊，一邊的點和另一邊的所有點相連
Partite sets
Thm.: bip. if and only if it has no cycle of odd length
Planar graph: can be drawn w/o crossing
- Dual of p. graph: place vertices at regions and join all vertices "near" it
  Fact: odd-sided poly. can not be divided into even-sided polygons
  (Pf: take dual, contradict with odd pt. thm.)
- planar even-sided graph
  Fact: any above graph is bip.
  (Pf: 你假設有一個odd cycle，那裡面一定要有一個點，和上一個fact矛盾)
Four color problem (thm.)
Thm.: any map on the plane can be colored by 4 colors
cube flip

大家一起協力合作拼出來的🤩

Ryota (Tanaka教授的學生) 中午帶大家去吃非常好吃的鰻魚飯
天啊那個入口即化的鰻魚好吃到自認詞窮無法描述其美味